#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        // dp[left][right]标记从i到j是否是回文字串
        vector<vector<int>> dp(n, vector<int>(n));
        string ans;
        // length表示判断的字串的长度
        // left表示字串的左边起始位置
        // right表示字串的右边起始位置
        for(int length = 0; length < n; length++){
        // 0 < 5

        // 1 < 5

        // 2 < 5

            for(int left = 0; left + length < n; left++){
            // 0+0 < 5
            // 1+0 < 5
            // 2+0 < 5
            // 3+0 < 5
            // 4+0 < 5

            // 0+1 < 5
            // 1+1 < 5
            // 2+1 < 5
            // 3+1 < 5

            // 0+2 < 5
            // 1+2 < 5

                int right = left + length;
                // right = 0+0
                // right = 1+0
                // right = 2+0
                // right = 3+0
                // right = 4+0

                // right = 0+1
                // right = 1+1
                // right = 2+1
                // right = 3+1

                // right = 0+2
                // right = 1+2

                // 即字符串长度为1时，矩阵对角线
                if(length == 0) {
                // 0 == 0  // true
                // 0 == 0  // true
                // 0 == 0  // true
                // 0 == 0  // true
                // 0 == 0  // true

                // 1 == 0  // false
                // 1 == 0  // false
                // 1 == 0  // false
                // 1 == 0  // false
                // 1 == 0  // false

                // 2 == 0  // false
                // 2 == 0  // false

                    dp[left][right] = 1;
                    // dp[0][0] = 1;
                    // dp[1][1] = 1;
                    // dp[2][2] = 1;
                    // dp[3][3] = 1;
                    // dp[4][4] = 1;

                // 字符串长度为2的时候，只需判断两者是否相等
                } else if(length == 1) {
                // 1 == 1  // true
                // 1 == 1  // true
                // 1 == 1  // true
                // 1 == 1  // true

                // 2 == 1  // false
                // 2 == 1  // false

                    dp[left][right] = (s[left] == s[right]);
                    // dp[0][1] = (s[0] == s[1]) -> dp[0][1] = 0
                    // dp[1][2] = (s[1] == s[2]) -> dp[1][2] = 0
                    // dp[2][3] = (s[2] == s[3]) -> dp[2][3] = 0
                    // dp[3][4] = (s[3] == s[4]) -> dp[3][4] = 0

                // 字符串长度大于等于3之后
                } else{
                    // 其是否是回文串取决于当前left和right及更小一号的字符串
                    // 更新参考值为矩阵的左下方
                    dp[left][right] = (s[left] == s[right] && dp[left + 1][right - 1]);
                    // dp[0][2] = (s[0] == s[2] && dp[0 + 1][2 - 1]) -> dp[0][2] = (1 && 1)
                    // dp[1][3] = (s[1] == s[3] && dp[1 + 1][3 - 1]) -> dp[1][3] = (1 && 1)
                }

                // 如果当前left位置到right位置的字串能够构成回文串，
                // 并且现在长度+1后大于之前记忆中的子回文串的长度，那么更新回文串！
                // 这里也可以优化成记录起始位置和长度的两个int，返回时再截取
                if(dp[left][right] && (length + 1) > ans.size()){
                // 1 && 0+1 > 0  // 1 && 1 -> true
                // 1 && 0+1 > 1  // 1 && 0 -> false
                // 1 && 0+1 > 1  // 1 && 0 -> false
                // 1 && 0+1 > 1  // 1 && 0 -> false
                // 1 && 0+1 > 1  // 1 && 0 -> false

                // 0 && 1+1 > 1  // 0 && 1 -> false
                // 0 && 1+1 > 1  // 0 && 1 -> false
                // 0 && 1+1 > 1  // 0 && 1 -> false
                // 0 && 1+1 > 1  // 0 && 1 -> false

                // 1 && 2+1 > 1  // 1 && 1 -> true
                // 1 && 2+1 > 2  // 1 && 1 -> true

                    ans = s.substr(left, length + 1);
                    // ans = s.substr(0,1)  // 将字符串s的第一个字符开始取一个字符赋值给ans

                    // ans = s.substr(1,3)  // 将字符串s的第一个字符开始取三个字符赋值给ans


                }
            }
        }
        return ans;
    }
};

class Solution1 {
public:
    string longestPalindrome(string s) {
        if(s.empty()){
            return "";
        }

        string ans = "";
        int n = s.size();
        vector<vector<int> > dp (n,vector<int>(n));

        for (int length = 0; length < n; length++) {
            for (int left = 0; left + length < n; ++left) {
                int right = left + length;

                if (length == 0){
                    dp[left][right] = 1;
                } else if (length == 1){
                    dp[left][right] = (s[left] == s[right]);
                } else{
                    dp[left][right] = (s[left] == s[right] && dp[left+1][right-1]);
                }

                if (dp[left][right] && (length+1) > ans.size()){
                    ans = s.substr(left,length+1);
                }
            }
        }
        return ans;
    }
};

int main(){
    string s = "abcbacba";
//    int n = s.size();
//    vector<vector<int>> dp(n, vector<int>(n));
//    string strs = "";
//    strs = s.substr(0,1);
//    strs = s.substr(1,1);
//    strs = s.substr(2,1);
//    strs = s.substr(3,1);
//    strs = s.substr(4,1);
//
    Solution1 s1;
    cout << s1.longestPalindrome(s) << endl;
//    for (int i = 0; i < dp.size(); i++) {
//        for (int j = 0; j < dp[i].size(); j++) {
//            cout << dp[i][j] << "\t";
//        }
//        cout << endl;
//    }
//
//    cout << strs << endl;
}